19.2 KB · ⇊ 6 parts · ⤓ Micron 19.2 KB · ⤓ HTML 64.0 KB

top

Unmwbq'mwbgespressione regolare (mwbwin inglese mwcaregular expression o, in forma abbreviata, mwcqregexp, mwcgregex o mwcwRE) è una sequenza di simboli (quindi una mwdastringa) che identifica un insieme di stringhe. Possono definire tutti e mwdqsoli i mwdglinguaggi regolari. Il mwdwteorema di Kleene afferma che la classe dei linguaggi regolari corrisponde alla classe dei linguaggi generati da mweagrammatiche di tipo 3 (nella mweqgerarchia di Chomsky) e riconosciuti da mwegautomi a stati finiti. Tuttavia, nella pratica esistono taluni costrutti (ad esempio i costrutti di backreference)cite-ref-1[1] che permettono di ampliare l'insieme di linguaggi definibili. mwgaProgrammi diversi supportano notazioni diverse per esprimere le stesse espressioni regolari, pertanto non esiste una mwgqsintassi "universale".

• Storia

• Descrizione

• Espressioni regolari nei linguaggi formali

• Impiego delle espressioni regolari

• Sintassi

• Espressioni regolari tradizionali di UNIX

• Esempi di quantificatori

• Note

• Bibliografia

• Voci correlate

• Altri progetti

• Collegamenti esterni

Sebbene fossero state formalizzate già fin dagli mwhqanni quaranta, le espressioni regolari entrarono nel mondo informatico per la prima volta alla fine degli mwhganni sessanta, in ambiente mwhwUnix: il primo mwiaeditor di testo che implementava funzioni che ne permettessero l'uso fu una versione di mwiqQED scritta da mwigKen Thompson, uno dei pionieri di Unix. L'editor, dalla sua mwiwinterfaccia a riga di comando, metteva a disposizione un comando chiamato mwjaglobal regular expression print, che successivamente fu reso un applicativo indipendente, mwjqmwjggrep.

Le espressioni regolari non ebbero grande diffusione ed utilizzo fino agli mwkaanni ottanta, quando fu inventato il mwkqlinguaggio di programmazione mwkgPerl che permetteva nativamente l'uso di espressioni regolari. La versatilità del linguaggio, dovuta anche al fatto d'essere un mwkwlinguaggio interpretato, ne permise l'utilizzo in svariate situazioni e favorì lo sviluppo del formalismo di Perl per le espressioni regolari, che diventò uno mwlastandard de facto. La grandissima diffusione di questi strumenti spinse gli sviluppatori a implementare le espressioni regolari anche in altri linguaggi, a mezzo di mwlqlibrerie come mwlgPCRE o persino come parte delle librerie standard di alcuni linguaggi, come mwlwJava e mwmatcl.

Un'espressione regolare definisce una mwmwfunzione che prende in ingresso una stringa, e restituisce in uscita un valore del tipo sì/no, a seconda che la stringa segua o meno un certo mwnapattern.

Ad esempio, tutti gli mwngindirizzi e-mail devono essere costituiti nel seguente modo: mwnwcominciare con una sequenza di caratteri alfanumerici, seguiti dal simbolo chiocciola, seguiti da altri caratteri alfanumerici, seguiti dal punto, seguiti da due o tre lettere.cite-ref-2[2] Questa regola informale diventerebbe una mwparegex qualora fosse codificata secondo una sintassi ben precisa e riconosciuta da un programma in grado di analizzare le stringhe.

Nei mwpwlinguaggi formali le espressioni regolari sono composte da costanti e operatori che denotano insiemi di stringhe, e da operazioni tra questi insiemi.

Dato un alfabeto finito mwqq Σ Σ {\displaystyle \Sigma } , sono definite le seguenti costanti:

1. mwra ∅ ∅ {\displaystyle \varnothing } o mwrq ∅ ∅ {\displaystyle \emptyset } (mwrginsieme vuoto)

2. mwsa ϵ ϵ {\displaystyle \epsilon } (stringa vuota, ovvero la mwsqstringa di lunghezza 0)

3. mwsw { a } {\displaystyle \left\{a\right\}} (carattere, mwta ∀ ∀ a ∈ ∈ Σ Σ {\displaystyle \forall a\in \Sigma } )

e le seguenti operazioni:

1. concatenazione: mwuaRS o mwuq R ∘ ∘ S {\displaystyle R\circ S} indica l'insieme mwug { α α β β | α α ∈ ∈ R ∧ ∧ β β ∈ ∈ S } {\displaystyle \left\{\alpha \beta |\alpha \in R\land \beta \in S\right\}}

2. unione: mwva R ∪ ∪ S {\displaystyle R\cup S} indica l'mwvqunione dei due insiemi

3. mwvwstella di Kleene: mwwa R ∗ ∗ {\displaystyle R^{*}} indica l'insieme che contiene tutte le possibili iterazioni ottenibili dagli elementi di mwwqR

4. intersezione: mwww R ∩ ∩ S {\displaystyle R\cap S} indica l'mwxaintersezione tra i due insiemi di stringhe

5. complemento: il complementare di mwxgR indica l'insieme delle stringhe appartenenti a mwxw Σ Σ ∗ ∗ ∖ ∖ R {\displaystyle \Sigma ^{*}\setminus R}

Ad esempio dati mwyq R = { a , b } {\displaystyle R=\left\{a,b\right\}} e mwyg S = { 7 , 8 } {\displaystyle S=\left\{7,8\right\}} , mwyw R S = { a 7 , b 7 , a 8 , b 8 } {\displaystyle RS=\left\{a7,b7,a8,b8\right\}} e mwza S ∗ ∗ = { ϵ ϵ , 7 , 8 , 77 , 78 , 87 , 88 , 777 , 778 , ⋯ ⋯ } {\displaystyle S^{*}=\left\{\epsilon ,7,8,77,78,87,88,777,778,\cdots \right\}}

Allora, possiamo dire che un'espressione regolare, definita a partire da un alfabeto mwzg Σ Σ {\displaystyle \Sigma } ed un insieme di simboli mwzw { + , ∗ ∗ , ( , ) , . , ∅ ∅ } {\displaystyle \left\{+,*,(,),.,\emptyset \right\}} , è una stringa mwaa R ∈ ∈ ( Σ Σ ∪ ∪ { + , ∗ ∗ , ( , ) , . , ∅ ∅ } ) + {\displaystyle R\in {\left(\Sigma \cup \left\{+,*,(,),.,\emptyset \right\}\right)}^{+}} che rende vera alcuna delle seguenti condizioni:

1. mwaw R = ∅ ∅ {\displaystyle R=\emptyset }

2. mwbq R ∈ ∈ Σ Σ {\displaystyle R\in \Sigma }

3. mwbw R = S + T {\displaystyle R=S+T} o mwca R = S T {\displaystyle R=ST} o mwcq R = S ∗ ∗ {\displaystyle R=S^{*}} , dove S e T sono espressioni regolari sull'alfabeto mwcg Σ Σ {\displaystyle \Sigma }

Le espressioni regolari sono utilizzate principalmente da mwdqeditor di testo per la ricerca e la sostituzione di porzioni del testo. Grande importanza rivestono inoltre nell'informatica teorica, nella quale, ad esempio, sono utilizzate per rappresentare tutti i possibili cammini su un mwdggrafo. Tuttavia, le espressioni regolari sono adatte a rappresentare un ristrettissimo insieme di linguaggi formali (se volessimo rappresentare espressioni aritmetiche o linguaggi di programmazione, avremmo già bisogno di utilizzare linguaggi di tipo 2): l'utilizzo dei linguaggi regolari è comunque conveniente, in quanto la chiusura degli stessi alle operazioni di unione, intersezione e complementazione, permettono la costruzione di un'mwdwalgebra di Boole e una buona capacità decisionale.

In base allo standard mwewPOSIX, la sintassi delle espressioni regolari in mwfaUNIX esiste in due versioni diverse:

• la sintassi detta mwfwdi base è quella che è stata creata per prima ed è la più diffusa: un esempio di applicativo che la usa è mwgamwgqed;

• la sintassi detta mwgwnuova, cioè quella che è stata definita con lo standard POSIX.2, viene usata ad esempio da mwhaegrep.

Quando è stata proposta la nuova versione della sintassi delle espressioni regolari, si è deciso di rendere obsoleta la versione vecchia, solo che oramai la diffusione della vecchia versione era tale che cambiare non era proficuocite-ref-3[3]. La maggior parte dei programmi che utilizzano le regexp, come mwigmwiwgrep e mwjamwjqsed, utilizzano tali regole di base fornendo al contempo supporto per le nuove regole estese. In questa sintassi, la maggior parte dei caratteri sono visti come letterali, e trovano solo se stessi; ad esempio: "a" trova "a"; "bc)" trova "bc)". Le eccezioni a questa regola sono i mwjgmetacaratteri:

Vecchie versioni di mwwagrep non supportano il separatore alternativo "|".

".atto" trova ogni stringa di cinque caratteri come mwxqgatto, mwxgmatto o mwxwpatto

"[gm]atto" trova mwyqgatto e mwygmatto

"[^p]atto" trova tutte le combinazioni dell'espressione ".atto" tranne mwzapatto

"^[gm]atto" trova mwzggatto e mwzwmatto ma solo all'inizio di una riga

"[gm]atto$" trova mw0qgatto e mw0gmatto ma solo alla fine di una riga

Dal momento che molte serie di caratteri variano a seconda della configurazione locale (in alcuni casi le lettere sono organizzate in abc..xyzABC...XYZ, in altri aAbB..yYzZ), lo standard POSIX ha definito alcune classi o categorie di caratteri come mostrato nella seguente tabella:

| classe POSIX | sintassi normale | significato |

|---|---|---|

| [:upper:] | [A-Z] | lettere maiuscole |

| [:lower:] | [a-z] | lettere minuscole |

| [:alpha:] | [A-Za-z] | lettera sia maiuscole che minuscole |

| [:alnum:] | [A-Za-z0-9] | numeri e lettere maiuscole e minuscole |

| [:digit:] | [0-9] | numeri |

| [:xdigit:] | [0-9A-Fa-f] | numeri in formato esadecimale |

| [:punct:] | [!\-"#$%&'()*+,.\/:;<=>?@[\]\^_`{/}~\\] | segni di interpunzione |

| [:blank:] | [ \t] | spazio o TAB |

| [:space:] | [ \t\n\r\f\v] | caratteri vuoti |

| [:cntrl:] | [\x00-\x1F\x7F] | caratteri control |

| [:graph:] | [^ \t\n\r\f\v] | caratteri non vuoti |

| [:print:] | [^\t\n\r\f\v] | caratteri non vuoti e spazi |

Le parentesi quadrate fanno parte della sintassi per indicare la classe di caratteri. Ad esempio mwaqw[[:upper:][:digit:]ab] trova corrispondenza in una qualsiasi lettera maiuscola, in una qualsiasi cifra, nella lettera 'a' minuscola e nella lettera 'b' minuscola.

• mwara* Cerca l'occorrenza (zero o più volte) del carattere o insieme di caratteri cui segue:

mwarmabc* identifica mwarqab seguito da zero o più mwaruc

come in mwarcab, mwargabc, mwarkabcc, mwaroabccc

• mwar0+ Cerca l'occorrenza (una o più volte) del carattere o insieme di caratteri cui segue:

mwasaab[ce]+ identifica mwaseab seguito da una o più mwasic oppure una o più mwasme

come in mwasuabc, mwasyabec, mwascabccc, mwasgabcceeecccccce

• mwass? Cerca l'occorrenza (zero o una volta) del carattere o insieme di caratteri cui segue:

mwas4abc? identifica mwas8ab seguito o meno da una mwatac

come in mwatiabc e mwatmab

• mwaty{m, n} Cerca l'occorrenza (da m a n volte; m lasciato vuoto è zero, n lasciato vuoto infinito) del carattere, insieme di caratteri o sotto-regex cui segue:

mwatk(ab){1,2} identifica le sequenze di uno o due mwatoab

come in mwatwab e mwat0abab

cite-note-11. ↑ mwauqmwauumwauyCostrutti di backreference nelle espressioni regolari, su mwauctechnet.microsoft.com, mwaugMicrosoft. mwaukURL consultato il 9 settembre 2014.

cite-note-22. ↑ In realtà la regola dovrebbe essere rifinita, in modo da supportare anche i simboli non alfanumerici che compaiono prima e dopo la chiocciola, ma in questo esempio semplice li trascuriamo.

cite-note-33. ↑ mwava(mwavemwaviEN) mwavmmwavqregex - POSIX.2 regular expressions, su mwavucl.cam.ac.uk. mwavyURL consultato il 17 gennaio 2014 mwavc(archiviato dall'mwavgurl originale il 4 marzo 2016).

• mwavw(EN) Regular expression, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

• mwawaGlob pattern

• mwawi^txt2regex$

Altri progetti

• Wikibooks

• Wikizionario

• Wikiversità

• Wikimedia Commons

• Wikibooks contiene un manuale sulle espressione regolare

• Wikizionario contiene il lemma di dizionario «espressione regolare»

• Wikiversità contiene una lezione riguardante i linguaggi ed espressioni regolari

• Wikimedia Commons contiene immagini o altri file sulle espressione regolare

• citerefopen-library(EN) Opere riguardanti regular expressions, su Open Library, Internet Archive.

• citerefmathworld(EN) Eric W. Weisstein, Regular Expression, su MathWorld, Wolfram Research.

• citereffoldoc(EN) Denis Howe, regular expression, in Free On-line Dictionary of Computing. Disponibile con licenza mwawkGFDL

• mwaws(EN) Regular expression, su fon.hum.uva.nl.

• Manuale di mwaw4Wikipedia sulle espressioni regolari